package rbm.modelado.estados;

import java.util.LinkedList;
import java.util.Vector;

import modelado.soluciones.SolucionListaImpl;

import rbm.modelado.datos.elementos.BlockPosNode;
import rbm.modelado.datos.elementos.BlockShapeImpl;
import rbm.modelado.datos.elementos.PointShapeImpl;
import rbm.modelado.datos.elementos.interfaces.BlockShape;
import rbm.modelado.datos.elementos.interfaces.BoardShape;
import rbm.modelado.datos.elementos.interfaces.Path;
import rbm.modelado.datos.elementos.interfaces.PointShape;
import rbm.modelado.datos.elementos.interfaces.MazeFloor;
import rbm.modelado.global.interfaces.PuzzleConstants;
import rbm.modelado.soluciones.SolucionRBMImpl;
import rbm.utiles.RollTester;
import rbm.utiles.TesterResults;

public class SolverLevel extends SolucionListaImpl implements PuzzleConstants {
	
	   private MazeFloor puzzleFloor;
	   private BoardShape board;
	   private Integer width;
	   private Integer height;
	   private PointShape finish;

	   private BlockPosNode[][] solverArray;

	   private BlockPosNode bestFinishNode;
	   private BlockPosNode mostBranchesNode;

	   private Integer nodeCounter;
	   private Integer totalLoopLength;
	   private Integer numLoops;

	   private LinkedList<BlockPosNode> queue;

	   private Vector<BlockPosNode> edgeList;	// list of all edges in full puzzle graph



	   public SolverLevel( MazeFloor pd )
	   {
		   puzzleFloor = pd;
	      board = puzzleFloor.getFloor();
	      width = board.getXDim();
	      height = board.getYDim();
	      finish = puzzleFloor.getCoordFinal();

	      solverArray = new BlockPosNode[width][height];
	      edgeList = new Vector<BlockPosNode>( 20 );
	   }



	   public SolucionRBMImpl solve()
	   {
		// queue of nodes to be expanded by breadth-first search
		  queue = new LinkedList<BlockPosNode>();

	      nodeCounter = 0;
	      totalLoopLength = 0;
	      numLoops = 0;

	      PointShape start = puzzleFloor.getCoordInic();


	      BlockPosNode startNode = updateArray( (Integer) start.getX(),(Integer) start.getY(),(BlockShape) puzzleFloor.getBlock(0).getShape(), 0, null,
	         START, 1, false );

	      queue.add( startNode );

	      bfSearch();

	      BlockPosNode longestPathNode = findLongestPathNode();

		// Use numLoops / 2 as each loop is counted twice

	      if( bestFinishNode == null )
	         return new SolucionRBMImpl( longestPathNode, mostBranchesNode, nodeCounter,
	            longestPathNode.getNumDirectionChanges(), totalLoopLength, numLoops / 2, edgeList );

	      Path path = bestFinishNode.tracePath();

	      SolucionRBMImpl sol = new SolucionRBMImpl( path, bestFinishNode, longestPathNode,
	         mostBranchesNode, nodeCounter, longestPathNode.getNumDirectionChanges(),
	            totalLoopLength, numLoops / 2, edgeList );

	      return sol;

	   }




		// Uses breadth first search. Quicker than depth first search, as otherwise the same paths
		// can be explored multiple times

	   private void bfSearch()
	   {
		  		  
	      while( queue.size() > 0 )
	      {

	         BlockPosNode currentNode = (BlockPosNode)queue.getFirst();
	         queue.removeFirst();

	         Integer x = currentNode.getXPos();
	         Integer y = currentNode.getYPos();
	         Integer moveNum = currentNode.getMinMoves();
	         Integer dir = currentNode.getLastMove();
	         Integer currBranch = currentNode.getNumBranches();
	         BlockShape shape = currentNode.getShape();


	         if( mostBranchesNode == null || mostBranchesNode.getNumBranches() <
	            currentNode.getNumBranches() )
	               mostBranchesNode = currentNode;

	         if( testComplete( shape, x, y ) )
	            if( bestFinishNode == null || bestFinishNode.getMinMoves() > moveNum )
	               bestFinishNode = currentNode;


	         TesterResults[] tr = new TesterResults[4];

	         tr[0] = RollTester.testRoll( puzzleFloor, shape, x, y, LEFT );
	         tr[1] = RollTester.testRoll( puzzleFloor, shape, x, y, RIGHT );
	         tr[2] = RollTester.testRoll( puzzleFloor, shape, x, y, UP );
	         tr[3] = RollTester.testRoll( puzzleFloor, shape, x, y, DOWN );

	         int branchCount = currBranch - 2;

	         for( int i = 0; i < 4; i++ )
	            if( tr[i].isLegal() )
	               branchCount++;


	         BlockPosNode nextNode;

	         if( dir != RIGHT && tr[0].isLegal() )
	         {
	            nextNode = updateArray( tr[0].getXPos(), tr[0].getYPos(), tr[0].getShape(),
	               moveNum + 1, currentNode, LEFT, branchCount, dir == LEFT );
	            if( nextNode != null )
	               queue.add( nextNode );
	         }

	         if( dir != LEFT && tr[1].isLegal() )
	         {
	            nextNode = updateArray( tr[1].getXPos(), tr[1].getYPos(), tr[1].getShape(),
	               moveNum + 1, currentNode, RIGHT, branchCount, dir == RIGHT );
	            if( nextNode != null )
	               queue.add( nextNode );
	         }

	         if( dir != DOWN && tr[2].isLegal() )
	         {
	            nextNode = updateArray( tr[2].getXPos(), tr[2].getYPos(), tr[2].getShape(),
	               moveNum + 1, currentNode, UP, branchCount, dir == UP );
	            if( nextNode != null )
	               queue.add( nextNode );
	         }

	         if( dir != UP && tr[3].isLegal() )
	         {
	            nextNode = updateArray( tr[3].getXPos(), tr[3].getYPos(), tr[3].getShape(),
	               moveNum + 1, currentNode, DOWN, branchCount, dir == DOWN );
	            if( nextNode != null )
	               queue.add( nextNode );
	         }
	      }
	   }



		// Checks if reached node is new
		// Returns current node if is new, null if not
		// Adds an edge to the edge list

	   private BlockPosNode updateArray( Integer x, Integer y, BlockShape shape, Integer moveNum,
	      BlockPosNode lastNode, Integer dir, Integer branch, Boolean dirCh )
	   {
	      BlockPosNode bpn = solverArray[x][y];

	      int numDirCh = 0;
	      if( lastNode != null )
	      {
	         numDirCh = lastNode.getNumDirectionChanges();
	         if( dirCh )
	            numDirCh++;
	      }

	      if( bpn == null )
	      {
	         BlockPosNode newNode = new BlockPosNode( x, y, shape, moveNum, lastNode, dir, branch, numDirCh );
	         solverArray[x][y] = newNode;
	         nodeCounter++;

	         if( lastNode != null )		// null when first node added
	            addEdge( lastNode, newNode );
	         return newNode;
	      }

	      else
	         return updateList( x, y, shape, moveNum, bpn, lastNode, dir, branch, numDirCh );
	   }



	   private BlockPosNode updateList( Integer x, Integer y, BlockShape shape, Integer moveNum, BlockPosNode bpn,
	      BlockPosNode lastNode, Integer dir, Integer branch, Integer numDirCh )
	   {

	      if( checkEqual( shape, bpn.getShape() ) )
	      {
	         addEdge( lastNode, bpn );
	         calculateLoopLength( bpn, lastNode );
	         return null;
	      }
	      else
	         if( bpn.getNextNode() == null )
	         {
	            BlockPosNode newNode = new BlockPosNode( x, y, shape, moveNum, lastNode, dir, branch, numDirCh );
	            bpn.addNode( newNode );
	            nodeCounter++;

	            addEdge( lastNode, newNode );
	            return newNode;
	         }
	         else
	            return updateList( x, y, shape, moveNum, bpn.getNextNode(), lastNode, dir, branch, numDirCh );

	   }



		// could potentially break if arrays used are not 'block' arrays,
		// eg if s1[m][n] and s1[m][p] are of different lengths

	   private static Boolean checkEqual( BlockShape shape1, BlockShape shape2 )
	   {
		   BlockShapeImpl s1 = (BlockShapeImpl)shape1; 
		   BlockShapeImpl s2 = (BlockShapeImpl)shape2;
		   
	      if( s1.getXDim() != s2.getXDim() || s1.getYDim()!= s2.getYDim() ||
	         s1.getZDim() != s2.getZDim() )
	            return false;

	      for( int i = 0; i < s1.getXDim(); i++ )
	         for( int j = 0; j < s1.getYDim(); j++ )
	            for( int k = 0; k < s1.getZDim(); k++ )
	            {
	               if( s1.getContentXYZ(i, j, k) != s2.getContentXYZ(i, j, k) )
	                  return false;
	            }

	      return true;
	   }


		// Node A is the node that has already been reached, node B is the
		// node that algorithm is processing
		// No of moves to node A is either same as to node B, or one more or less.
		// Each loop gets counted twice.

	   private void calculateLoopLength( BlockPosNode nodeA, BlockPosNode nodeB )
	   {
	      int length = 0;
	      int aMoves = nodeA.getMinMoves();
	      int bMoves = nodeB.getMinMoves();


		// Nodes reach each other this move number
	      if( aMoves == bMoves )
	      {
	         length = 0;
	      }

		// Node A reached quicker
	      else if( aMoves < bMoves )
	      {
	         if( !nodeB.isCountedInLoop() )
	         {
	            length++;
	            nodeB.setCountedInLoop();
	         }

	         nodeB = nodeB.getLastVisited();
	      }

	      else if( aMoves > bMoves )
	      {
	         if( !nodeA.isCountedInLoop() )
	         {
	            length++;
	            nodeA.setCountedInLoop();
	         }

	         nodeA = nodeA.getLastVisited();
	      }


		// Tracing back path from each will find the node where the
		// path first split into loop

	      nodeA.setCountedInLoop();
	      nodeB.setCountedInLoop();

	      while( nodeA != nodeB )
	      {
	         if( !nodeA.isCountedInLoop() )
	         {
	            nodeA.setCountedInLoop();
	            length++;
	         }

	         if( !nodeB.isCountedInLoop() )
	         {
	            nodeA.setCountedInLoop();
	            length++;
	         }

	         nodeA = nodeA.getLastVisited();
	         nodeB = nodeB.getLastVisited();

	      }

	      totalLoopLength += length;
	      numLoops++;
	   }



		// Go through each finish square to see if covered, then count
		// number of blocks in bottom layer of shape. If same as number
		// of finish squares, then completed

	   private boolean testComplete( BlockShape shape, Integer xPos,
	      Integer yPos )
	   {
		   PointShapeImpl finishAux = (PointShapeImpl)finish;
		   BlockShapeImpl shapeAux = (BlockShapeImpl)shape;

	      for( int n = 0; n < finishAux.getDim(); n += 2 )
	      {
	         if( finishAux.getN(n) - xPos < 0 || finishAux.getN(n) - xPos >= shapeAux.getXDim() ||
	             finishAux.getN(n+1) - yPos < 0 || finishAux.getN(n+1) - yPos >= shapeAux.getYDim() )
	                return false;

	         if( !shapeAux.getContentXYZ(finishAux.getN(n)- xPos, finishAux.getN(n+1) - yPos, 0) )
	            return false;
	      }

	      int count = 0;

	      for( Integer i = 0; i < shapeAux.getXDim(); i++ )
	         for( Integer j = 0; j < shapeAux.getYDim(); j++ )
	            if( shapeAux.getContentXYZ(i, j, 0) )
	               count++;

	      if( 2 * count == finishAux.getDim() )
	         return true;
	      else
	         return false;

	   }


	   private BlockPosNode findLongestPathNode()
	   {
	      BlockPosNode longestPathNode = null;
	      BlockPosNode currentNode;

	      for( int i = 0; i < solverArray.length; i++ )
	         for( int j = 0; j < solverArray[0].length; j++ )
	         {
	            currentNode = solverArray[i][j];

	            while( currentNode != null )
	            {
	               if( longestPathNode == null || longestPathNode.getMinMoves() <
	                  currentNode.getMinMoves() )
	               {
	                  longestPathNode = currentNode;
	               }

	               currentNode = currentNode.getNextNode();
	            }
	         }
	      return longestPathNode;

	   }


		// Some edges can be added twice by the algorithm, such as when
		// an edge completes a cycle. Scans vector looking for pairs of
		// nodes in the opposite order, means edge has already been added

	   private void addEdge( BlockPosNode n1, BlockPosNode n2 )
	   {

	      boolean already = false;

	      for( int i = 0; i < edgeList.size(); i += 2 )
	      {

	         if( edgeList.elementAt( i ) == n2 && edgeList.elementAt( i+1 ) == n1 )
	         {
	            already = true;
	            break;
	         }
	      }

	      if( !already )
	      {
	         edgeList.add( n1 );
	         edgeList.add( n2 );
	      }

	   }
}
